20210212 CF701 div2

我完成的

A 500

想让结果 a 变大，底数 b 加一，还是指数加一的问题

我：我记录下了上上次和上次，如果上次>上上次，那么继续算，我这种思路似乎更快（实际上不用存储两次，存 1 次就行，看这次比上次大还是小），实际上 b 的取值一定小于 30，否则没有意义，可以遍历。

题解：暴力遍历 b

B 1000

相似的递增数组，相似定义为有且只有一个位置不不一样

我：考虑 al 和 ar 之间的每个数，如果是换 al 会怎样，换 ar 会怎样，如果 al、ar 中间只有一个有多少种，有 2 个有多少种……最后猜系数，猜常数

题解：考虑替换成为的值是 x，如果 x<al 那么怎么样，x 在 al 和 ar 之间会怎样……

我不会的

C 1500

给定 a，b 的范围，求 a%b 与 a//b 相同的情况的个数。

我的想法：遍历 b，可以每种情况 O(1) 确定有多少 a。但是 b 上限 10^9，搞不定

题解：a，b 上限为 x，y。设 a%b=a//b=k，可知 k<=根号 x，遍历 k，每种情况 O(1) 确定有多少 a，b。方法为，可知 b 属于[1,y]，同时 a=kb+k 属于[1,x]，因此数量为
max(0,min(y,x/k−1)−k)max(0,min(y,x/k−1)−k)

收获：对于数学题，除了一般化 ->特殊化 ->找规律之外，不必清楚的认识规律，只要能发现数量级的关系，或者找到适合的不等式，保证约束是充分的，那么范围内都是解

D 1750

给一个矩阵 A，找到一个矩阵 B，B 的相邻元素（i 或 j 差 1 的元素）的差的绝对值为 k^4，且 B 的每一个元素都是对应位置 A 的元素的倍数。

题解：这个问题不能硬算，因为每一个 B 中的值要影响上下左右 4 个值，又要考虑 A，这不可能暴力。A 里所有元素都在 0~16 之间，那就找到 1~16 的公因数 720720，先填满 B 中不相邻的所有格子，之后剩下的一半格子填上 720720+aij，就满足题意了。
收获：这个题目挺取巧的，数学题，关键就是不能怕，观察数据范围非常重要，切入点也非常重要。这个题就没有规律可找，不是那种规律题，只能考虑有没有数字满足所有数据范围的要求。

E 2500

一棵树，红蓝两点从根结点出发，每次红结点只能走当前结点的孩子，蓝结点每次可以走到下一层任意的结点上，红蓝每走完一次都可以互换位置（也可以不换），积分方式是每层上红蓝结点位置的点权差值的绝对值，求最大积分

题解：dpi 表示红结点每一轮结束在第 i 个结点时的最大积分，可以通过之前的 dp 值求解。那么 dpj 就考虑如果 j 结点没有交换，那么最大值就是 j 结点这一层的最大数或最小数与 j 的绝对值的差 +dpj 的父亲。如果 j 结点发生了交换，那么最大值就是 dp 上一层某节点 + 该节点孩子与 j 的绝对值之差。

我的收获：dp 中也可以进行分类讨论，应该首先讨论简单的情况，对于 dp 表示状态的变量的确定一定要慎重。这个题用红点的位置作为变量是非常精妙的。

F 3000

给定一个数组 b，确定满足条件的数组 a 的个数。其中条件为，bi=ai 或 bi=a 从第一项累加到 ai。

我的想法：b 中每个点要表态，是累加还是相等，这个题复杂度就爆炸了，因为要确定累加和相等是不是不同，那就要枚举所有方案，这是根本行不通的。有点像背包问题，应该是 dp 优化

题解：
n^2logn 解法：dpi,j 代表 b 从 1 到 i 组成的数组找到的 a 数组个数，要求这些 a 数组和为 j。我们知道 dpi,j 可以推导出 dpi+1,j+bi（选择 bi=ai 且 j！=0），也可以推导出 dpi+1,bi（选择 bi 等于 sum），最终结果就是 dpn 那一行的和
nlogn 解法：可以用这个算法优化 "Venice technique"，因为不需要用 multiset，一个 map 就足够了，我们用不到找最小/最大序列。

我的收获：说实话感觉自己做不出来，没怎么看懂，懂了大概意思那种。EF 这种难度的 dp 对我来说还是太难了，E 还好点，F 真的太难了。